﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CPF_experement
{
    class BasicIndepandetSubproblemNewAlogoritem
    {
        LinkedList<IndepandentGroup> allGroups;
        public int totalCost;
        public int max_group;
        public int min_group;

        public BasicIndepandetSubproblemNewAlogoritem(AgentState[] allAgentsState)
        {
            totalCost = 0;
            max_group = 0;
            min_group = allAgentsState.Length;
            this.allGroups = new LinkedList<IndepandentGroup>();
            foreach (AgentState start in allAgentsState)
            {
                AgentState[] firstGroups=new AgentState[1];
                firstGroups[0] = start;
                this.allGroups.AddFirst(new IndepandentGroup(firstGroups));
            }

        }
        public void solve()
        {
            bool stop;
            LinkedListNode<IndepandentGroup> tempA = allGroups.First;
            LinkedListNode<IndepandentGroup> tempB;
            while (tempA!=null)
            {
                tempA.Value.solve();
                if (tempA.Value.solution == null || tempA.Value.solution[0] == null)
                {
                    totalCost = -2;
                    Console.WriteLine("Out of time");
                    return;
                }
                tempB = allGroups.First;
                stop = false;
                while (tempB!=tempA && !stop)
                {
                    if (tempA.Value.isColaiding(tempB.Value))
                    {
                        tempA.Value.join(tempB.Value);
                        allGroups.Remove(tempB);
                        stop = true;
                    }
                    tempB = tempB.Next;
                }
                if (!stop)
                    tempA = tempA.Next;
            }
            foreach (IndepandentGroup subAns in allGroups)
            {
                if (subAns.startingPos.Length > max_group)
                {
                    max_group = subAns.startingPos.Length;
                }
                if (subAns.startingPos.Length < min_group)
                {
                    min_group = subAns.startingPos.Length;
                }
                totalCost += subAns.totalCost;
            }
             Console.WriteLine("Total cost - " + totalCost);

        }
    }
    class IndepandentGroup
    {
        public AgentState[] startingPos;
        public LinkedList<PoinForNewAlgoritem>[] solution;
        public int totalCost;


        public IndepandentGroup(AgentState[] startingPos)
        {
            this.startingPos = startingPos;
        }

        public void solve()
        {
            SuperTree st = new SuperTree(startingPos);
            solution = st.solve();
            totalCost=st.totalCost;
        }

        public bool isColaiding(IndepandentGroup other)
        {
            LinkedList<PoinForNewAlgoritem>[] first = this.solution;
            LinkedList<PoinForNewAlgoritem>[] second = other.solution;
            bool thisIsLonger = true;
            if (first[0].Count<second[0].Count)
            {
                thisIsLonger = false;
                first = second;
                second = this.solution;
            }
            HashSet<PoinForNewAlgoritem> closedList = new HashSet<PoinForNewAlgoritem>();
            for (int i = 0; i < first.Length; i++)
            {
                foreach (PoinForNewAlgoritem reserved in first[i])
                {
                    closedList.Add(reserved);
                }
            }
            for (int i = 0; i < second.Length; i++)
            {
                PoinForNewAlgoritem lastReserved;
                if (thisIsLonger)
                {
                    lastReserved = new PoinForNewAlgoritem(other.startingPos[i].pos_X, other.startingPos[i].pos_Y, -1, 0);
                }
                else
                {
                    lastReserved = new PoinForNewAlgoritem(this.startingPos[i].pos_X, this.startingPos[i].pos_Y, -1, 0);
                }
                foreach (PoinForNewAlgoritem reserved in second[i])
                {
                    if (closedList.Contains(reserved.getColaidingPoint())) return true;
                    if (closedList.Contains(reserved.copyPointNoDirection())) return true;
                    lastReserved = reserved;
                }
                for (int j = second[i].Count + 1; j <= first[0].Count; j++)
                {
                    lastReserved = lastReserved.parkedAgent();
                    if (closedList.Contains(lastReserved.copyPointNoDirection())) return true;
                }
            }
            return false;
        }

        public IndepandentGroup join(IndepandentGroup other)
        {
            AgentState[] temp = new AgentState[startingPos.Length + other.startingPos.Length];
            int i;
            for (i = 0; i < startingPos.Length; i++)
            {
                temp[i] = startingPos[i];
            }
            for (int j = 0; j < other.startingPos.Length; j++)
            {
                temp[i + j] = other.startingPos[j];
            }
            startingPos = temp;
            return this;
        }
    }
    
}
